package org.yimon.tool.algo.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: ym.gao
 * @description: 无重复字符的最长字串
 * @date: 2024/7/22 下午7:38
 */
public class LeetCode_003_LengthOfLongestSubstring {

    public static void main(String[] args) {
        System.out.println(LeetCode_003_LengthOfLongestSubstring.lengthOfLongestSubstring("abcabcbb"));
    }

    public static String lengthOfLongestSubstring(String s) {
        //特殊情况判断
        if (s == null || s.isEmpty()) {
            return null;
        }
        //用set集合记录不重复的字符
        Set<Character> noDup = new HashSet<>();
        String maxLengthStr = s.substring(0, 1);
        for (int left = 0; left < s.length(); left++) {//左指针
            if (left > 0) {//这里就是进行左指针移动与noDup匹配的关键点的关键点
                noDup.remove(s.charAt(left - 1));
            }
            int right = left + noDup.size();
            for (; right < s.length(); right++) {//右指针移动
                if (noDup.contains(s.charAt(right))) {//存在重复的情况结束当前窗口
                    break;
                } else {
                    noDup.add(s.charAt(right));//不存在则添加到noDup中
                }
            }
            maxLengthStr = right - left > maxLengthStr.length() ? s.substring(left, right) : maxLengthStr;//每次获取最大长度
        }
        return maxLengthStr;
    }
}
